package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-15 21:23
 */
public class Q72 {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if(i == 0){
                    dp[i][j] = j;
                }
                if(j == 0) {
                    dp[i][j] = i;
                }
                if(i > 0 && j > 0) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                    if(s1[i - 1] == s2[j - 1]){
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1]);
                    }
                }
            }
        }

        return dp[m][n];
    }
}
